package com.zr.service.intelligent;

import com.alibaba.fastjson.JSON;
import com.alibaba.fastjson.JSONArray;
import com.alibaba.fastjson.JSONObject;
import com.zr.dao.base.BaseCityDao;
import com.zr.vo.base.BaseCity;
import org.springframework.stereotype.Service;
import javax.annotation.Resource;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import static com.zr.utils.LngAndLatUtil.loadJSON;
@Service
public class Distance {
    static int INF=(int)1e7;//设置无穷大的值为10的七次方
    static int N=100;
    static double [][]g=new double[N][N];//地图的无向带权邻接矩阵
    static int []x=new int[N];//记录当前路径
    static int []bestx=new int[N];//记录当前最优路径
    static double cl;//当前路径长度
    static double bestl;//当前最短路径长度
    static int n,m;//城市个数n,边数m
    @Resource
    private BaseCityDao baseCityDao;

    static void swap(int array[], int a, int b) {//交换函数
        int temp;
        temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }

    static void Traveling(int t) {
        if (t > n) {//到达叶子节点
            /*
            最后一个城市与住地城市有边相连并且路径长度比当前最优值小，说明找到了一条更好的路径，记录相关信息
             */
            if (g[x[n]][1] != INF && (cl + g[x[n]][1] < bestl)) {
                for (int j = 1; j <= n; j++) {
                    bestx[j] = x[j];
                }
                bestl = cl + g[x[n]][1];
            }
        } else {
            //没有到达叶子节点
            //搜索扩展节点的所有分支
            for (int j = t; j <= n; j++) {
                if (g[x[t - 1]][x[j]] != INF && (cl + g[x[t - 1]][x[j]] < bestl)) {
                    //如果第t-1个城市与第t个城市有边相连并且有可能得到更短的路线
                    swap(x, t, j);
                    //交换两个元素的值
                    cl = cl + g[x[t - 1]][x[t]];
                    //从第t+1层的扩展结点继续搜索
                    Traveling(t+1);
                    //第t+1层搜索完毕，回溯到第t层
                    cl=cl-g[x[t-1]][x[t]];
                    swap(x,t,j);
                }
            }
        }
    }

    //初始化函数
    static void init() {
        bestl = INF;
        cl = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = i; j <= n; j++) {
                g[i][j] = g[j][i] = INF;
            }
        }
        for (int i = 0; i <= n; i++) {
            x[i] = i;
            bestx[i] = 0;
        }
    }

    static void print(){
        System.out.print("最短路径");
        for (int i=1;i<=n;i++){
            System.out.print(bestx[i]+"---->");
        }
        System.out.println("1");
        System.out.println("最短路径长度："+bestl);
        System.out.println("*************");
        for (int i=0;i<=n;i++){
            System.out.println(Arrays.toString(g[i]));
        }

    }

    /**
     * 传入城市数，连接数，城市间距离二维数组
     * @param cityNum
     * @param roadNum
     * @param distance
     * @return
     */
    public static String route(int cityNum,int roadNum,double [][] distance){
        n=cityNum;
        init();
        m=roadNum;
        for (int j=0;j<m;j++){
            g[(int) distance[j][0]][(int) distance[j][1]]=g[(int) distance[j][1]][(int) distance[j][0]]=distance[j][2];
        }
        Traveling(2);
        return Arrays.toString(bestx);
    }

    public void test(){
        List<Integer> cityIds=new ArrayList<>();
        cityIds.add(120100);
        cityIds.add(130300);
        cityIds.add(131100);
        cityIds.add(140500);
        cityIds.add(140900);
        cityIds.add(320000);
        cityIds.add(210800);
        cityIds.add(150400);
        cityIds.add(220100);
        cityIds.add(230500);
        cityIds.add(310000);
        cityIds.add(320500);
        double[][] road=this.road(cityIds);
        System.out.println(route(cityIds.size(),road.length,road));
        print();
    }

    public double[][] road(List<Integer> cityIdList){
        List<BaseCity> cityList=new ArrayList<>();
        for (Integer cityId:cityIdList) {
            cityList.add(baseCityDao.selectByPrimaryKey(cityId));
        }
        int size=0;
        for (int i = 1; i < cityIdList.size(); i++) {
            size+=(cityIdList.size()-i);
        }
        double[][] road=new double[size][];
        List<double[]> doubles=new ArrayList<>();
        int i = 0;
        for (; i < cityList.size(); i++) {
            StringBuilder destination=new StringBuilder();
            destination.append(cityList.get(i).getLongitude());
            destination.append(",");
            destination.append(cityList.get(i).getLatitude());
            StringBuilder orgins=new StringBuilder();
            for (int j = i+1; j <  cityList.size(); j++) {
                orgins.append(cityList.get(j).getLongitude());
                orgins.append(",");
                orgins.append(cityList.get(j).getLatitude());
                if(j<cityList.size()-1){
                    orgins.append("|");
                }

            }
            String url = "https://restapi.amap.com/v3/distance?origins="+orgins+"&destination="+destination+"&key=870a2505da2303f0fd87c9eb66519f01&output=json、";
            String json = loadJSON(url);
            JSONObject obj = JSON.parseObject(json);
            System.out.println(obj.toString());
            if(obj.get("status").toString().equals("1")) {
                JSONArray jsonArray = obj.getJSONArray("results");
                for (int j = 0; j < jsonArray.size(); j++) {
                    JSONObject objectInArray = jsonArray.getJSONObject(j);
                    double distance = objectInArray.getDouble("distance");
//                    double duration = objectInArray.getDouble("duration");
                    double originId=objectInArray.getDouble("origin_id")+1+i;
                    doubles.add(new double[]{i+1,originId,distance});
                }
            }

        }
        for (int k = 0; k < doubles.size(); k++) {
            road[k]=new double[3];
            for (int j = 0; j < 3; j++) {
                road[k][j] =(doubles.get(k))[j];
            }
        }
        return road;
    }
}
